package leetcode_161_180;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;

public class fractionToDecimal_166 {
    public String fractionToDecimal(int numerator, int denominator) {
        /**
         * 模拟除法本身并不难
         * 想法是对每一次运算产生的余数存入hash表，出现重复余数就说明进入了循环
         * 题目又保证 答案字符串的长度有限，不存在无线不循环小数
         *
         * StringBuilder 底层使用的char数组，效率太低
         * 2ms
         */
        long  numer =  numerator,denom= denominator;

        if(numer%denom==0 )
            return  String.valueOf(numer /denom);

        //都转化为正数进行计算
        boolean isPlus= numerator>0 && denominator>0 || numerator<0 && denominator<0;
        numer=numer>0?numer:-numer;
        denom=denom>0?denom:-denom;

        String s= String.valueOf(numer/denom);  //小数点应该的位置

        StringBuilder ans=new StringBuilder();
        HashMap<Long,Integer> reminders=new HashMap<>();  //每次计算的余数以及该计算的坐标位置
        int index=0;
        boolean flag=false;   //是否是循环小数
        while(numer%denom!=0){
            //除数不够用时
            while (numer<denom){
                ans.append("0");        //结果补0
                numer*=10;         //除数*10
                index++;
                reminders.put(numer,index);  //每次尝试除以除数都应该记录进余数中
            }
            //记录当前位数，更新被除数
            int num= (int) (numer/denom);
            ans.append(num);
            index+=String.valueOf(num).length();
            numer=numer%denom*10;

            if(reminders.containsKey(numer)){    //出现重复余数
                int left=reminders.get(numer);
                ans.insert(left,"(");
                ans.insert(left<s.length()?s.length()+1:s.length(),".");
                ans.append(")");
                flag=true;
                break;
            }
            reminders.put(numer,index);   //添加余数
        }
        if (!flag) {
            if(numer!=0) ans.append(numer / denom);
            ans.insert(s.length(), ".");
        }
        return isPlus?ans.toString():"-"+ans.toString();
    }


    /**
     * 高解，核心思路一模一样
     * 但是思路清晰，代码简洁
     */
    public String fractionToDecimal2(int numerator, int denominator) {
        StringBuilder sb = new StringBuilder();
        long a = numerator, b = denominator;
        if (a > 0 && b < 0 || a < 0 && b > 0) sb.append('-');
        a = Math.abs(a);
        b = Math.abs(b);
        sb.append(a / b);
        if (a % b == 0) return sb.toString();
        sb.append('.');
        Map<Long, Integer> map = new HashMap<>();
        while ((a = (a % b) * 10) > 0 && !map.containsKey(a)) {
            map.put(a, sb.length());
            sb.append(a / b);
        }
        if (a == 0) return sb.toString();
        return sb.insert(map.get(a).intValue(), '(').append(')').toString();
    }
}
